#include<iostream>
#include<vector>
#define MIN_INT -10000
using namespace std;

 struct ListNode {
     int val;
     ListNode *next;
     ListNode() : val(0), next(nullptr) {}
     ListNode(int x) : val(x), next(nullptr) {}
     ListNode(int x, ListNode *next) : val(x), next(next) {}
 };

    void show(ListNode* l)
    {
        ListNode* show = l;
        cout<<"the list is:"<<endl;
        while(show)
        {
            cout<<show->val<<" ";
            show = show -> next;
        }
        cout<<endl;
    }
 ListNode* mergeKLists(vector<ListNode*>& lists) {
    if(lists.size() == 0) 
        return nullptr;
    ListNode* mergedList = lists[0];
    if(mergedList == nullptr && lists.size() <= 1)
    {
        return mergedList;
    }
    ListNode* head = new ListNode(0, mergedList);
    for(int i=1;i<lists.size();i++)
    {
        mergedList = head;
        ListNode* cur2 = new ListNode(0, lists[i]);
        while(mergedList -> next || cur2 -> next)
        {
            int val1 = mergedList -> next ? mergedList->next->val : 10000;
            int val2 = cur2 -> next ? cur2->next->val : 10000;
            cout<<"val1:"<<val1<<" val2:"<<val2<<endl;
            if(val1 > val2)
            {
                ListNode* temp = mergedList -> next? mergedList->next : nullptr;
                mergedList -> next = new ListNode(val2);
                //cout<<"cur1->next:"<<mergedList -> next->val<<endl;
                cur2 = cur2 -> next;
                mergedList = mergedList -> next;
                mergedList -> next = temp;    
            }else{
                mergedList = mergedList -> next;
            }
        }
        //delete cur1,cur2;
        //show(mergedList);
    }
    return head -> next;
}


int main()
{
    vector<ListNode*> lists;
    // ListNode* list1 = new ListNode(1);
    // ListNode* list2 = new ListNode(4);
    // ListNode* list3 = new ListNode(5);
    // lists.push_back(list1);
    // lists.push_back(list2);
    // lists.push_back(list3);
    ListNode* list1 = nullptr;
    ListNode* list2 = new ListNode(1);
    lists.push_back(list1);
    lists.push_back(list2);


    // cout<<"enter list:"<<endl;
    // for(int i=0;i<3;i++)
    // {
    //     ListNode* cur = lists[i];
    //     for(int j=0;j<3;j++)
    //     {
    //         ListNode* next = new ListNode();
    //         cin>>next->val;
    //         cur -> next = next;
    //         cur = cur -> next;
    //     }
    // }


    // cout<<"the list is:"<<endl;
    // for(int i=0;i<3;i++)
    // {
    //     ListNode* cur = lists[i];
    //     for(int j=0;j<4;j++)
    //     {
    //         cout<<cur->val<<" ";
    //         cur = cur -> next;
    //     }
    //     cout<<endl;
    // }
    ListNode* result = mergeKLists(lists);
    cout<<"the result is:"<<endl;
    while(result)
    {
        cout<<result->val<<" ";
        result = result -> next;
    }
    
    return 0;
}